Теорема Поста

Система булевых функций $B$ является полной тогда и только тогда, когда она не содержится целиком ни в одном из пяти предполных классов (Поста): $T_{0}, T_{1}, S, M, L$. $$ \langle B \rangle = P_{2} \iff \forall{K \in \{T_{0}, T_{1}, S, M, L\}}\mathpunct{:}~~ B \not\subseteq K $$

$\Large{\implies}$ Все классы Поста $K \in \{T_{0}, T_{1}, S, M, L\}$ являются замкнутыми и отличными от $P_{2}$. Если $B \subseteq K$, то в силу замкнутости $\langle B \rangle \subseteq K \neq P_{2}$, следовательно, система $B$ не является полной. $\Large{\impliedby}$ Пусть $B$ не содержится ни в одном из классов. Значит, существуют функции (некоторые могут совпадать): $f_{0} \notin T_{0},~ f_{1} \notin T_{1},~ f_{s} \notin S,~ f_{m} \notin M,~ f_{l} \notin L$. Докажем, что формулами над $B$ можно выразить отрицание и конъюнкцию. Так как система $\{\land, \neg\}$ полная, отсюда будет следовать полнота $B$. Алгоритм получения констант и отрицания, а затем с помощью лемм о нелинейной/немонотонной функции — конъюнкции, представлен на схеме: !post-proof.png В итоге получаем базис $\{\land, \neg\}$, а значит $B$ — полная система. $\square$